package com.yoshino.leetcode.oneHundred.twentyfourth;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int cuttingRope(int n) {
        // 拆分后的数 > 4 时，可以拆分为更好的解：x > 4 => 2(x - 2) > x
        // 即拆分的值只能为{1, 2, 3}
        // 1没有实际意义，{2, 3}
        // 2 的个数不能超过 3个：2 * 2 * 2 < 3 * 3
        if (n < 4) {
            return n - 1;
        }
        int pow = n / 3, mod = n % 3;
        if (mod == 0) {
            return (int) Math.pow(3, pow);
        } else if (mod == 1) {
            return (int) Math.pow(3, pow - 1) * 4;
        } else {
            return (int) Math.pow(3, pow) * 2;
        }
    }

    public int[][] findContinuousSequence(int target) {
        // 必须是连续整数列
        List<int[]> resList = new ArrayList<>();
        int sum = 0;
        for (int l = 1, r = 1; r < target; ) {
            sum += r;
            while (sum > target) {
                sum -= l++;
            }
            if (sum == target) {
                int[] temp = new int[r - l + 1];
                for (int i = 0; i < temp.length; i++) {
                    temp[i] = l + i;
                }
                resList.add(temp);
            }
            r++;
        }
        int[][] res = new int[resList.size()][];
        for (int i = 0; i < resList.size(); i++) {
            res[i] = resList.get(i);
        }
        return res;
    }

    public int lastRemaining(int n, int m) {
        /*
        思路：使用数学方法(先举例)
                你要知道最后的结果是3，带着结果去看问题

            第一次，【0, 1, 2, 3, 4】，本轮要踢出2                                  看3
            (下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
            第二次，【3, 4, 0, 1】，本轮要踢出0                                     看1
            第三次，【1, 3, 4】，本轮要踢出4                                        看1
            第四次，【1, 3】 本轮要踢出1                                            看3
            第五次，【3】
            最后返回3

            我们要使用的数学方法，就是从结果0号位置，反推最开始在哪
            你从第二次，向上看第一次
            你会发现，原来3在0的位置
                    现在，3在(0 + 3) % 5
                            => +3 回到上次的位置
                            => %5 防止数组溢出，并且数组本来就是循环数组

            f(n) = ( f(n - 1) + m ) % n
            解释意思：
                f(n) 表示上一次
                f(n - 1) 表示这次，因为我们要从这次回推上一次
                m 表示隔几个
                n表示上一次的数组长
        */
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }
}